;; Largest product in a grid

;; Problem 11

;; In the 20×20 grid below, four numbers along a diagonal
;; line have been marked in red.

;; 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
;; 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
;; 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
;; 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
;; 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
;; 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
;; 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
;; 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
;; 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
;; 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
;; 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
;; 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
;; 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
;; 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
;; 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
;; 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
;; 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
;; 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
;; 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
;; 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

;; The product of these numbers is 26 × 63 × 78 × 14 =
;; 1788696.

;; What is the greatest product of four adjacent numbers in
;; the same direction (up, down, left, right, or diagonally)
;; in the 20×20 grid?


(import
 (except (rnrs base)
         let-values
         map)
 (only (guile)
       lambda* λ)
 (ice-9 match)
 (ice-9 futures))


(define %numbers-as-strings
  '("08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08"
    "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00"
    "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65"
    "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91"
    "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80"
    "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50"
    "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70"
    "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21"
    "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72"
    "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95"
    "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92"
    "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57"
    "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58"
    "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40"
    "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66"
    "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69"
    "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36"
    "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16"
    "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54"
    "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"))



(define split-at-space
  (λ (str)
    (string-split str (λ (c) (char=? c #\space)))))


(define numbers
  (let ([numbers
         (map (λ (list-of-number-strings)
                (map string->number list-of-number-strings))
              (map split-at-space %numbers-as-strings))])
    (let ([dim-spec 2])
      (list->array dim-spec numbers))))


;; IDEA 1: We only need to check 4 out of 8 directions. The
;; ones which "go forward" in the array, because the other
;; directions will only contain reversed orders of numbers
;; and result in the same products. The forward directions
;; are: right, right-down, down, down-left.

;; IDEA 2: We do not need to go all the way to the 20th row
;; or 20th column for all of the directions. For example for
;; the direction right-down, we only need to check products
;; up to the row 17 and column 17. For row 18 or column 18
;; there will not be a sufficient number of factors left in
;; that direction to calculate the product from.

;; IDEA 3: Predicates can be defined to check for a given
;; position, whether a direction needs to be checked.

;; IDEA 4: Predicates can be provided with arguments, which
;; make them generally applicable for arrays of arbitrary
;; size and for arbitrary number of factors.

(define go-right?
  (λ (row-count col-count factors-count row col)
    "Taking into account the number of rows and columns in
the grid, the number of factors to be used to calculate a
product and the current row and column, decide, whether
there are sufficient factors in the direction right are
available."
    (<= col (- col-count factors-count))))


(define go-right-down?
  (λ (row-count col-count factors-count row col)
    (and (<= col (- col-count factors-count))
         (<= row (- row-count factors-count)))))


(define go-down?
  (λ (row-count col-count factors-count row col)
    (<= row (- row-count factors-count))))


(define go-down-left?
  (λ (row-count col-count factors-count row col)
    (and (>= col (- factors-count 1))
         (<= row (- row-count factors-count)))))

;; IDEA 5: To make the code more readable, we can define
;; procedures to mode one step in a direction in the array,
;; returning the coordinates of the next factor.

(define next-right
  (λ (row col)
    (cons row (+ col 1))))

(define next-right-down
  (λ (row col)
    (cons (+ row 1) (+ col 1))))

(define next-down
  (λ (row col)
    (cons (+ row 1) col)))

(define next-down-left
  (λ (row col)
    (cons (+ row 1) (- col 1))))

;; IDEA 6: Define a data abstraction for coordinates, to
;; keep things readable and adaptable later.

(define make-coordinates
  (λ (row col)
    (cons row col)))

(define coordinates-row
  (λ (coords)
    (car coords)))

(define coordinates-col
  (λ (coords)
    (cdr coords)))

;; IDEA 7: Then we can define on top of these one step
;; procedures another procedure, which gives all required
;; factors for calculating a product.

(define get-factors
  (λ (numbers row col factors-count next)
    (cond
     [(= factors-count 0) '()]
     [else
      (cons (array-ref numbers row col)
            (match-let ([(next-row . next-col) (next row col)])
              (get-factors numbers
                           next-row
                           next-col
                           (- factors-count 1)
                           next)))])))

;; IDEA 5: The number of factors can be given as an
;; argument, to make the algorithm more general.

(define find-greatest-product
  (λ (numbers factors-count)
    (match-let ([(row-count col-count non-existing ...) (array-dimensions numbers)])
      (display (simple-format #f "row count: ~a\n" row-count))
      (display (simple-format #f "col count: ~a\n" col-count))
      (let iter-rows ([row 0] [rows-max-product 0])
        (let iter-cols ([col 0] [cols-max-product 0])
          (display (simple-format #f "row: ~a\n" row))
          (display (simple-format #f "col: ~a\n" col))
          (cond
           ;; If rows exhausted, return the result.
           [(>= row row-count) rows-max-product]
           ;; Start with next row.
           [(>= col col-count)
            (iter-rows (+ row 1)
                       ;; Compare maximum product of this
                       ;; row with the previous maximum
                       ;; products of other rows. Choose the
                       ;; maximum of both.
                       (max rows-max-product cols-max-product))]
           [else
            ;; Go to the next number in the grid.
            (iter-cols
             (+ col 1)
             ;; Take the maximum of the products of all
             ;; directions. Use 0 as a default, if not
             ;; checking a direction, because a predicate
             ;; says that the direction does not contain a
             ;; sufficient number of factors.
             (max cols-max-product
                  (or (and (go-right? row-count col-count factors-count row col)
                           (apply * (peek (get-factors numbers row col factors-count next-right))))
                      0)
                  (or (and (go-right-down? row-count col-count factors-count row col)
                           (apply * (peek (get-factors numbers row col factors-count next-right-down))))
                      0)
                  (or (and (go-down? row-count col-count factors-count row col)
                           (apply * (peek (get-factors numbers row col factors-count next-down))))
                      0)
                  (or (and (go-down-left? row-count col-count factors-count row col)
                           (apply * (peek (get-factors numbers row col factors-count next-down-left))))
                      0)))]))))))


(display
 (simple-format
  #f "~a\n"
  (find-greatest-product numbers 4)))
